<!doctype html>



  


<html class="theme-next mist use-motion" lang="en">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.0" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="how to write fast code," />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.0" />






<meta name="description" content="M3-1What’s the Difference between Multicore and Manycore?">
<meta property="og:type" content="article">
<meta property="og:title" content="how to write fast code - Module 3">
<meta property="og:url" content="https://annashuo.github.io/2017/03/17/笔记3/index.html">
<meta property="og:site_name" content="Anna's Blog">
<meta property="og:description" content="M3-1What’s the Difference between Multicore and Manycore?">
<meta property="og:image" content="https://raw.githubusercontent.com/Annashuo/hello-world/master/module3.png">
<meta property="og:image" content="https://raw.githubusercontent.com/Annashuo/hello-world/master/OPL.png">
<meta property="og:updated_time" content="2017-03-21T13:41:58.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="how to write fast code - Module 3">
<meta name="twitter:description" content="M3-1What’s the Difference between Multicore and Manycore?">
<meta name="twitter:image" content="https://raw.githubusercontent.com/Annashuo/hello-world/master/module3.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Mist',
    sidebar: {"position":"right","display":"post"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://annashuo.github.io/2017/03/17/笔记3/"/>





  <title> how to write fast code - Module 3 | Anna's Blog </title><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
<!-- hexo-inject:begin --><!-- hexo-inject:end --><script>
  window.fbAsyncInit = function() {
    FB.init({
      appId      : '',
      xfbml      : true,
      version    : 'v2.6'
    });
  };

  (function(d, s, id){
     var js, fjs = d.getElementsByTagName(s)[0];
     if (d.getElementById(id)) {return;}
     js = d.createElement(s); js.id = id;
     js.src = "//connect.facebook.net/en/sdk.js";
     fjs.parentNode.insertBefore(js, fjs);
   }(document, 'script', 'facebook-jssdk'));
</script>



<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-105321506-1', 'auto');
  ga('send', 'pageview');
</script>


  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?6f5ab2ef1e021070500f7228c830f3c6";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>








  
  
    
  

  <div class="container one-collumn sidebar-position-right page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">Anna's Blog</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
    
      <p class="site-subtitle">My heart is in the work...</p>
    
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            Archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            Tags
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
  <link itemprop="mainEntityOfPage" href="https://annashuo.github.io/2017/03/17/笔记3/">

  <span style="display:none" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <meta itemprop="name" content="Anna">
    <meta itemprop="description" content="">
    <meta itemprop="image" content="/images/avatar.gif">
  </span>

  <span style="display:none" itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
    <meta itemprop="name" content="Anna's Blog">
    <span style="display:none" itemprop="logo" itemscope itemtype="http://schema.org/ImageObject">
      <img style="display:none;" itemprop="url image" alt="Anna's Blog" src="">
    </span>
  </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                how to write fast code - Module 3
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2017-03-17T20:00:08-04:00">
                2017-03-17
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/STUDY/" itemprop="url" rel="index">
                    <span itemprop="name">STUDY</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2017/03/17/笔记3/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count fb-comments-count" data-href="https://annashuo.github.io/2017/03/17/笔记3/" itemprop="commentCount">0</span> comments
                </a>
              </span>
            
          

          

          
          

          

          

        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <h3 id="M3-1"><a href="#M3-1" class="headerlink" title="M3-1"></a>M3-1</h3><h4 id="What’s-the-Difference-between-Multicore-and-Manycore"><a href="#What’s-the-Difference-between-Multicore-and-Manycore" class="headerlink" title="What’s the Difference between Multicore and Manycore?"></a>What’s the Difference between Multicore and Manycore?</h4><a id="more"></a>
<ul>
<li><p>Multicore: Optimized for reducing execution latency for a few threads</p>
<ul>
<li>Sophisticated instruction controls, large caches</li>
<li>Each core optimized for executing a single thread</li>
</ul>
</li>
<li><p>Manycore: Assumes 1000-way concurrency readily availabel in applications</p>
<ul>
<li>More resources dedicated to compute</li>
<li>Cores optimized for aggregate throughput, deemphasizing individual performance</li>
</ul>
</li>
</ul>
<h4 id="When-does-using-a-GPU-make-sense"><a href="#When-does-using-a-GPU-make-sense" class="headerlink" title="When does using a GPU make sense?"></a>When does using a GPU make sense?</h4><ul>
<li>Applications with a lot of concurrency</li>
<li>Some memory intensive applications</li>
<li>Advantage diminidhes when task granularity becomes too large to fit in shared memory</li>
</ul>
<h4 id="What-is-the-memory-hierarchy-inversion-And-why-is-it-there"><a href="#What-is-the-memory-hierarchy-inversion-And-why-is-it-there" class="headerlink" title="What is the memory hierarchy inversion? And why is it there?"></a>What is the memory hierarchy inversion? And why is it there?</h4><p>Memory hierarchy inversion: the higher level memory L1 or L2 cache are actually smaller than the register file.</p>
<p>Because there is shared memory.</p>
<h4 id="What-is-the-memory-wall-How-to-get-around-it"><a href="#What-is-the-memory-wall-How-to-get-around-it" class="headerlink" title="What is the memory wall? How to get around it?"></a>What is the memory wall? How to get around it?</h4><p>Memory wall: performance gap between a processor and the piece of memory, that is getting longer, and longer to fetch a piece of data from memory to process in the processor.</p>
<p>Manycore processors utilize application concurrency to hide memory latency.</p>
<h4 id="Why-warps"><a href="#Why-warps" class="headerlink" title="Why warps?"></a>Why warps?</h4><p>Warps: Software abstraction to hide an extra level of architextural complexity</p>
<p>1 Streaming Mulprocessor(SM)= at most 8 blocks</p>
<p>1 block=??? warps</p>
<p>1 warp=32 threads. (32-wide SIMD)</p>
<h4 id="How-do-we-deal-with-GPUs-of-different-sizes"><a href="#How-do-we-deal-with-GPUs-of-different-sizes" class="headerlink" title="How do we deal with GPUs of different sizes?"></a>How do we deal with GPUs of different sizes?</h4><p>Well what CUDA provides is an abstraction, that, can scale across all these different sizes. A thread block is a bock of threads that can execute at the same time while sharing some context. ComputaIon is grouped into blocks of independent, concurrently executable work</p>
<h4 id="What-are-the-implications-of-the-thread-block-abstraction"><a href="#What-are-the-implications-of-the-thread-block-abstraction" class="headerlink" title="What are the implications of the thread block abstraction?"></a>What are the implications of the thread block abstraction?</h4><ul>
<li><p>Threads are the computation performed in each SIMD lane in a core</p>
<ul>
<li>CUDA provides a SIMT programming abstraction to assist users</li>
</ul>
</li>
<li><p>SIMT: Single Instruction Multiple Threads</p>
<ul>
<li>A single instruction controls multiple processing element</li>
<li>Different from SIMD – SIMD exposes the SIMD width to the programmer</li>
<li>SIMT abstract the #threads in a thread block as a user - specified parameter</li>
</ul>
</li>
<li><p>SIMT enables programmers to write thread-level parallel code for    </p>
<ul>
<li>Independent,scalarthreads</li>
<li>Data-parallel code for coordinated threads</li>
</ul>
</li>
<li>For functional correctness, programmers can ignore SIMT behavior</li>
<li>For performance, programmers can tune applications with SIMT in mind</li>
</ul>
<h4 id="How-do-threads-communicate-with-each-other"><a href="#How-do-threads-communicate-with-each-other" class="headerlink" title="How do threads communicate with each other?"></a>How do threads communicate with each other?</h4><p>Using shared memory and L1 cache.</p>
<p><img src="https://raw.githubusercontent.com/Annashuo/hello-world/master/module3.png" alt="module3"></p>
<h4 id="What-is-the-caveat-in-synchronizing-threads-in-a-thread-block"><a href="#What-is-the-caveat-in-synchronizing-threads-in-a-thread-block" class="headerlink" title="What is the caveat in synchronizing threads in a thread block?"></a>What is the caveat in synchronizing threads in a thread block?</h4><p>__syncthreads()</p>
<ul>
<li>waits until all threads in the thread block have reached this point and all global and shared memory accesses made by these threads prior to __syncthreads() are visible to all threads in the block</li>
<li>used to coordinate communication between the threads of the same block</li>
</ul>
<h4 id="CUDA-Function-Types"><a href="#CUDA-Function-Types" class="headerlink" title="CUDA Function Types"></a>CUDA Function Types</h4><ul>
<li>_<em>global_</em><ul>
<li>Executed on the device</li>
<li>Callable from the host only</li>
<li>_<em>global_</em> functions must have void return type</li>
<li>Any call to a _<em>global_</em> function must specify its execution configuration &lt;&lt;&lt; &gt;&gt;&gt;</li>
<li>A call to a _<em>global_</em> function is asynchronous</li>
</ul>
</li>
<li>_<em>device_</em><ul>
<li>Executed on the device</li>
<li>Callable from the device only</li>
</ul>
</li>
<li>_<em>host_</em><ul>
<li>Executed on the host</li>
<li>Callable from the host only</li>
</ul>
</li>
</ul>
<h3 id="M3-2"><a href="#M3-2" class="headerlink" title="M3-2"></a>M3-2</h3><h4 id="What-are-the-three-ways-to-improve-execution-throughput"><a href="#What-are-the-three-ways-to-improve-execution-throughput" class="headerlink" title="What are the three ways to improve execution throughput?"></a>What are the three ways to improve execution throughput?</h4><ul>
<li><p>Maximizing Memory Throughput</p>
<ul>
<li>SoA vs AoS</li>
<li>Memory coalescing</li>
<li>Use of shared memory</li>
<li>Memory bank conflict</li>
<li>Padding</li>
</ul>
</li>
<li><p>Maximizing Instruction Throughput</p>
</li>
<li>Maximizing Scheduling Throughput</li>
</ul>
<h4 id="When-to-use-SOA-vs-AOS"><a href="#When-to-use-SOA-vs-AOS" class="headerlink" title="When to use SOA vs AOS?"></a>When to use SOA vs AOS?</h4><p>Example one: You have a list of coordinates, and you want to find the distance from the origin to all points</p>
<ul>
<li>Struct of Array(<strong>better</strong>): index all these x, y, and z’s with the thread ID. for each thread we’re actually picking out one of these index. And we would have multiple of these threads executing at the same time.</li>
<li>Array of Struct(<strong>worse</strong>): each thread is going to be loading operands from memory locations with a certain stride. In order to satisfy the operand for one operation it actually needs to go to memory and load a bunch of things that are not gonna be used for a particular calculation. And without any sort of shared memory buffering.</li>
</ul>
<p>Example two: Find the distance from the origin to a list of points estimated to be ~1% of all points</p>
<ul>
<li>Struct of Array(<strong>worse</strong>): we are gonna have a huge strides between all these consecutive elements.</li>
<li>Array of Struct(<strong>better</strong>): we’re gonna be loading chunks of these tuples at a time so that we can be more efficient in loading blocks of memory at a time. We’re better utilizing the memory bandwidth by loading these consecutive elements for each array at a time</li>
</ul>
<h4 id="What-is-memory-Coalescing-When-to-use-it-Why-is-it-important"><a href="#What-is-memory-Coalescing-When-to-use-it-Why-is-it-important" class="headerlink" title="What is memory Coalescing? When to use it? Why is it important?"></a>What is memory Coalescing? When to use it? Why is it important?</h4><p>Memory Coalescing: Combine multiple memory accesses generated from multiple threads into a single physical transaction.</p>
<p>It happens when memory access.</p>
<p>It can increase DRAM memory bandwidth and throughput.</p>
<p>Some rules for maximizing DRAM memory bandwidth: </p>
<ul>
<li>Possible bus transaction sizes: 32B, 64B,128B</li>
<li>Memory segment must be aligned: First address = multiple of segment size</li>
<li>Hardware coalescing for each half-warps: 16-word wide </li>
</ul>
<h4 id="What-is-shared-memory-How-to-use-it"><a href="#What-is-shared-memory-How-to-use-it" class="headerlink" title="What is shared memory? How to use it?"></a>What is shared memory? How to use it?</h4><p>Registers and shared memory are on-chip memories. Variables that reside in these types of memory can be accessed at very high speed in a highly parallel manner.</p>
<p>Registers are allocated to individual threads; each thread can only access its own registers.</p>
<p>Shared memory is allocated to thread blocks; all threads in a block can access variables in the shared memory locations allocated to the block. Shared memory is an efficient means for threads to cooperate by sharing their input data and the intermediate results of their work.</p>
<p>How to use shared memory?</p>
<ul>
<li>Declared a fixed sized variable at compile time</li>
<li>Define a size to be used at run time</li>
</ul>
<h4 id="What-is-memory-bank-conflict-How-to-work-around-it"><a href="#What-is-memory-bank-conflict-How-to-work-around-it" class="headerlink" title="What is memory bank conflict? How to work around it?"></a>What is memory bank conflict? How to work around it?</h4><p>Shared memory has 32 banks. Each bank has a bandwidth of 32 bits per two clock cycles(2 cycle latency)</p>
<p>A bank conflict occurs if two or more threads access any bytes within <strong>different 32-bit words belonging to the same bank</strong>.</p>
<p>Using padding technique to offset memory bank conflicts.</p>
<h4 id="What-is-branch-divergence"><a href="#What-is-branch-divergence" class="headerlink" title="What is branch divergence?"></a>What is branch divergence?</h4><p>Branch divergence occurs only within a warp. Full efficiency is realized when all 32 threads of a warp agree on their path. To optimize, factor out decision variables to have shorter sequence of divergent code.</p>
<h4 id="How-to-optimize-for-instruction-mix"><a href="#How-to-optimize-for-instruction-mix" class="headerlink" title="How to optimize for instruction mix?"></a>How to optimize for instruction mix?</h4><p>Compiler Assisted Loop Unrolling(In CUDA, #pragma unroll)</p>
<h4 id="What-is-occupancy-How-to-model-measure-it"><a href="#What-is-occupancy-How-to-model-measure-it" class="headerlink" title="What is occupancy? How to model/measure it?"></a>What is occupancy? How to model/measure it?</h4><p>Occupancy: </p>
<ul>
<li>Ability of a CUDA kernel to occupy concurrent contexts in a SM(Streaming Multiprocessor)</li>
<li>Specifically, the ratio of active warps to the maximum number of warps supported</li>
<li>Helpful in determining how efficient the kernel could be on the GPU</li>
</ul>
<h4 id="How-to-use-the-code-profiler-with-CUDA"><a href="#How-to-use-the-code-profiler-with-CUDA" class="headerlink" title="How to use the code profiler with CUDA?"></a>How to use the code profiler with CUDA?</h4><p>CUDA Profiler Tutorial – by Erik Reed</p>
<h3 id="M3-3"><a href="#M3-3" class="headerlink" title="M3-3"></a>M3-3</h3><h4 id="What-are-the-important-properties-of-a-Map-function"><a href="#What-are-the-important-properties-of-a-Map-function" class="headerlink" title="What are the important properties of a Map function?"></a>What are the important properties of a Map function?</h4><p>Map: a function that applies a given function to each element of a list and return a list of result.</p>
<p>Two properties:</p>
<ul>
<li>Side-effect free: Only returning a value, no modificaGons of state with the rest of the application</li>
<li>Independent: Has an independent piece of work, where its input does not depend on another function</li>
</ul>
<h4 id="What-are-the-important-properties-of-a-Reduce-function"><a href="#What-are-the-important-properties-of-a-Reduce-function" class="headerlink" title="What are the important properties of a Reduce function?"></a>What are the important properties of a Reduce function?</h4><p>Reduce: A function that takes in a list of objects and builds a return value</p>
<p>Three properties:</p>
<ul>
<li>Associativity</li>
<li>Allows elements to be reduced in parallel in a “tree”</li>
<li>In CUDA, the synchronization has to be managed by the programmer</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div></pre></td><td class="code"><pre><div class="line">//totally log2(blockDim.x) iterations, all have branch divergence</div><div class="line">unsigned int i=threadIdx.x;</div><div class="line">for(unsigned int stride=1; stride&lt;blockDim.x; stride*=2)&#123;</div><div class="line">	_syncthreads();</div><div class="line">	if(t%(2*stride)==0)</div><div class="line">		sum[t]+=sum[t+stride];</div><div class="line">&#125;</div><div class="line">// another version: only 5 iterations have branch divergence</div><div class="line">for(unsigned int stride=blockDim.x/2; stride&gt;1; stride/=2)&#123;</div><div class="line">	_syncthreads();</div><div class="line">	if(t&lt;stride)</div><div class="line">		sum[t]+=sum[t+stride];</div></pre></td></tr></table></figure>
<h4 id="What-are-the-important-properties-of-a-Scan-function"><a href="#What-are-the-important-properties-of-a-Scan-function" class="headerlink" title="What are the important properties of a Scan function?"></a>What are the important properties of a Scan function?</h4><p>Scan(Prefix Sum):<br>Takes a binary associative operator ⊕ with identity I, and an array of n elements [a0, a1, …, an-1] and returns the ordered set [I, a0, (a0 ⊕ a1), …, (a0 ⊕ a1 ⊕ … ⊕ an-2)].</p>
<p>Trust library of CUDA</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line">#include &lt;thrust/scan.h&gt;          int data[6] = &#123;1, 0, 2, 2, 1, 3&#125;;  </div><div class="line">thrust::exclusive_scan(data, data + 6, data); // in-place scan   // data is now &#123;0, 1, 1, 3, 5, 6&#125;</div></pre></td></tr></table></figure>
<h4 id="How-to-compact-an-array-in-a-data-parallel-way"><a href="#How-to-compact-an-array-in-a-data-parallel-way" class="headerlink" title="How to compact an array in a data-parallel way?"></a>How to compact an array in a data-parallel way?</h4><p>Compaction: Removing elements from an array - take in an array, and produce an shorter array</p>
<ul>
<li>Map–create flags(“1”keep,“0”remove)    </li>
<li>Scan–compute index</li>
<li>Map–copy to new array</li>
</ul>
<h4 id="How-to-find-unique-elements-in-an-array-in-a-data-parallel-way"><a href="#How-to-find-unique-elements-in-an-array-in-a-data-parallel-way" class="headerlink" title="How to find unique elements in an array in a data-parallel way?"></a>How to find unique elements in an array in a data-parallel way?</h4><p>FindUniq: Removing duplicates from an array – take in an set, produces a equal or smaller set of unique values</p>
<ul>
<li>Sort</li>
<li>Map – flag when ith and (i-1)th element differ [0] = 1</li>
<li>Scan–create compaction index</li>
<li>Map–copy to new array</li>
</ul>
<h3 id="M3-4"><a href="#M3-4" class="headerlink" title="M3-4"></a>M3-4</h3><h4 id="What-are-parallel-software-patterns"><a href="#What-are-parallel-software-patterns" class="headerlink" title="What are parallel software patterns?"></a>What are parallel software patterns?</h4><p>A parallel software pattern is a generalizable solution to a class of recurring problems that occurs in the design of parallel software.</p>
<h4 id="What-are-the-three-goals-the-software-patterns-aim-to-achieve"><a href="#What-are-the-three-goals-the-software-patterns-aim-to-achieve" class="headerlink" title="What are the three goals the software patterns aim to achieve?"></a>What are the three goals the software patterns aim to achieve?</h4><ul>
<li>Define a set of vocabularies to communicate</li>
<li>Present a set of expert techniques for beginners to learn</li>
<li>Allows experts to more quickly design complex systems</li>
</ul>
<h4 id="What-is-a-software-architecture"><a href="#What-is-a-software-architecture" class="headerlink" title="What is a software architecture?"></a>What is a software architecture?</h4><p>A software architecture is ahierarchical composition of:</p>
<ul>
<li>Computational patterns – the atoms</li>
<li>Structural patterns – the molecular bonds</li>
</ul>
<h4 id="How-is-it-important-for-writing-fast-code"><a href="#How-is-it-important-for-writing-fast-code" class="headerlink" title="How is it important for writing fast code?"></a>How is it important for writing fast code?</h4><h4 id="What-are-the-five-categories-of-patterns-in-OPL"><a href="#What-are-the-five-categories-of-patterns-in-OPL" class="headerlink" title="What are the five categories of patterns in OPL?"></a>What are the five categories of patterns in OPL?</h4><p><img src="https://raw.githubusercontent.com/Annashuo/hello-world/master/OPL.png" alt="OPL"></p>
<h4 id="What-are-the-nine-sections-in-an-OPL-pattern"><a href="#What-are-the-nine-sections-in-an-OPL-pattern" class="headerlink" title="What are the nine sections in an OPL pattern?"></a>What are the nine sections in an OPL pattern?</h4>
      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        

      
    </div>


    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/how-to-write-fast-code/" rel="tag"># how to write fast code</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/03/16/笔记2/" rel="next" title="how to write fast code - Module 2">
                <i class="fa fa-chevron-left"></i> how to write fast code - Module 2
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/04/06/笔记4/" rel="prev" title="how to write fast code - Module 4">
                how to write fast code - Module 4 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>

          
          </div>
          


          
  <div class="comments" id="comments">
    
      <div class="fb-comments"
           data-href="https://annashuo.github.io/2017/03/17/笔记3/"
           data-numposts="10"
           data-width="100%"
           data-colorscheme="light">
      </div>
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            Overview
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/images/avatar.gif"
               alt="Anna" />
          <p class="site-author-name" itemprop="name">Anna</p>
          <p class="site-description motion-element" itemprop="description">My heart is in the work...</p>
        </div>
        <nav class="site-state motion-element">
        
          
            <div class="site-state-item site-state-posts">
              <a href="/archives">
                <span class="site-state-item-count">43</span>
                <span class="site-state-item-name">posts</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-categories">
              <a href="/categories">
                <span class="site-state-item-count">6</span>
                <span class="site-state-item-name">categories</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">12</span>
                <span class="site-state-item-name">tags</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/Annashuo/Annashuo.github.io" target="_blank" title="GitHub">
                  
                    <i class="fa fa-fw fa-github"></i>
                  
                  GitHub
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://weibo.com/u/1861044584?is_all=1" target="_blank" title="Weibo">
                  
                    <i class="fa fa-fw fa-weibo"></i>
                  
                  Weibo
                </a>
              </span>
            
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#M3-1"><span class="nav-number">1.</span> <span class="nav-text">M3-1</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#What’s-the-Difference-between-Multicore-and-Manycore"><span class="nav-number">1.1.</span> <span class="nav-text">What’s the Difference between Multicore and Manycore?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#When-does-using-a-GPU-make-sense"><span class="nav-number">1.2.</span> <span class="nav-text">When does using a GPU make sense?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-the-memory-hierarchy-inversion-And-why-is-it-there"><span class="nav-number">1.3.</span> <span class="nav-text">What is the memory hierarchy inversion? And why is it there?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-the-memory-wall-How-to-get-around-it"><span class="nav-number">1.4.</span> <span class="nav-text">What is the memory wall? How to get around it?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Why-warps"><span class="nav-number">1.5.</span> <span class="nav-text">Why warps?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-do-we-deal-with-GPUs-of-different-sizes"><span class="nav-number">1.6.</span> <span class="nav-text">How do we deal with GPUs of different sizes?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-implications-of-the-thread-block-abstraction"><span class="nav-number">1.7.</span> <span class="nav-text">What are the implications of the thread block abstraction?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-do-threads-communicate-with-each-other"><span class="nav-number">1.8.</span> <span class="nav-text">How do threads communicate with each other?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-the-caveat-in-synchronizing-threads-in-a-thread-block"><span class="nav-number">1.9.</span> <span class="nav-text">What is the caveat in synchronizing threads in a thread block?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#CUDA-Function-Types"><span class="nav-number">1.10.</span> <span class="nav-text">CUDA Function Types</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#M3-2"><span class="nav-number">2.</span> <span class="nav-text">M3-2</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-three-ways-to-improve-execution-throughput"><span class="nav-number">2.1.</span> <span class="nav-text">What are the three ways to improve execution throughput?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#When-to-use-SOA-vs-AOS"><span class="nav-number">2.2.</span> <span class="nav-text">When to use SOA vs AOS?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-memory-Coalescing-When-to-use-it-Why-is-it-important"><span class="nav-number">2.3.</span> <span class="nav-text">What is memory Coalescing? When to use it? Why is it important?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-shared-memory-How-to-use-it"><span class="nav-number">2.4.</span> <span class="nav-text">What is shared memory? How to use it?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-memory-bank-conflict-How-to-work-around-it"><span class="nav-number">2.5.</span> <span class="nav-text">What is memory bank conflict? How to work around it?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-branch-divergence"><span class="nav-number">2.6.</span> <span class="nav-text">What is branch divergence?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-to-optimize-for-instruction-mix"><span class="nav-number">2.7.</span> <span class="nav-text">How to optimize for instruction mix?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-occupancy-How-to-model-measure-it"><span class="nav-number">2.8.</span> <span class="nav-text">What is occupancy? How to model/measure it?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-to-use-the-code-profiler-with-CUDA"><span class="nav-number">2.9.</span> <span class="nav-text">How to use the code profiler with CUDA?</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#M3-3"><span class="nav-number">3.</span> <span class="nav-text">M3-3</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-important-properties-of-a-Map-function"><span class="nav-number">3.1.</span> <span class="nav-text">What are the important properties of a Map function?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-important-properties-of-a-Reduce-function"><span class="nav-number">3.2.</span> <span class="nav-text">What are the important properties of a Reduce function?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-important-properties-of-a-Scan-function"><span class="nav-number">3.3.</span> <span class="nav-text">What are the important properties of a Scan function?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-to-compact-an-array-in-a-data-parallel-way"><span class="nav-number">3.4.</span> <span class="nav-text">How to compact an array in a data-parallel way?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-to-find-unique-elements-in-an-array-in-a-data-parallel-way"><span class="nav-number">3.5.</span> <span class="nav-text">How to find unique elements in an array in a data-parallel way?</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#M3-4"><span class="nav-number">4.</span> <span class="nav-text">M3-4</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-parallel-software-patterns"><span class="nav-number">4.1.</span> <span class="nav-text">What are parallel software patterns?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-three-goals-the-software-patterns-aim-to-achieve"><span class="nav-number">4.2.</span> <span class="nav-text">What are the three goals the software patterns aim to achieve?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-is-a-software-architecture"><span class="nav-number">4.3.</span> <span class="nav-text">What is a software architecture?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#How-is-it-important-for-writing-fast-code"><span class="nav-number">4.4.</span> <span class="nav-text">How is it important for writing fast code?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-five-categories-of-patterns-in-OPL"><span class="nav-number">4.5.</span> <span class="nav-text">What are the five categories of patterns in OPL?</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#What-are-the-nine-sections-in-an-OPL-pattern"><span class="nav-number">4.6.</span> <span class="nav-text">What are the nine sections in an OPL pattern?</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Anna</span>
</div>


<div class="powered-by">
  Powered by <a class="theme-link" href="https://hexo.io">Hexo</a>
</div>

<div class="theme-info">
  Theme -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Mist
  </a>
</div>


        

        
      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  




  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.0"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.0"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.0"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.0"></script>



  



  




	





  





  

  
      <!-- UY BEGIN -->
      <script type="text/javascript" src="http://v2.uyan.cc/code/uyan.js?uid="></script>
      <!-- UY END --><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({"tex2jax":{"inlineMath":[["$","$"],["\\(","\\)"]],"skipTags":["script","noscript","style","textarea","pre","code"],"processEscapes":true},"TeX":{"equationNumbers":{"autoNumber":"AMS"}}});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->
  




  
  

  
  


  

  

  


</body>
</html>
